#include <iostream>
using std::cout;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 计算A和B的长度
        int numA = 0;
        int numB = 0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA)
        {
            curA = curA->next;
            numA ++;
        }
        while(curB)
        {
            curB = curB->next;
            numB ++;
        }

        int diff;
        curA = headA;
        curB = headB;
        if(numA > numB)
        {
            diff = numA - numB;
            while(diff --)
            {
                curA = curA->next;
            }
        }
        else
        {
            diff = numB - numA;
            while (diff --)
            {
                curB = curB->next;
            }
            
        }

        while(curA != nullptr)
        {
            if(curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

int main(int argc, char const *argv[])
{
    ListNode *head = new ListNode();
    head->val = 1;
    head->next = nullptr;
    ListNode *cur = head;
    for (int i = 1; i < 5; ++i)
    {
        ListNode *newNode = new ListNode();
        newNode->next = nullptr;
        newNode->val = i + 1;
        cur->next = newNode;
        cur = newNode;
    }
    cur = head;
#if 1
    while (cur)
    {
        if (cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
#endif
    Solution s;
    // head = s.removeNthFromEnd(head, 3);
    cur = head;
    // cur = s.swapPairs(head);
    while (cur)
    {
        if (cur->next != nullptr)
            cout << cur->val << "->";
        else
            cout << cur->val << "\n";

        cur = cur->next;
    }
    getchar();
    return 0;
}
